﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RecursiveOther
{
	//递归思想
	//概念: 递归，说白了就是直接或者间接的调用自己的一种算法。它是把求解问题转化为规模较小的子问题，然后通过多次递归一直到可以得出结果的最小解，然后通过最小解逐层向上返回调用，最终得到整个问题的解。总之递归可以概括为一句话就是：“能进则进，不进则退”。
	/*
	 * 二：三要素
      <1>  递归中每次循环都必须使问题规模有所缩小。
      <2>  递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。
      <3>  当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。

		三： 注意
       <1>  前面也说了，递归必须要有一个递归出口。
       <2>  深层次的递归会涉及到频繁进栈出栈和分配内存空间，所以运行效率比较低，当问题规模较大时，不推荐使用。
       <3>  在递归过程中，每次调用中的参数，方法返回点，局部变量都是存放在堆栈中的，如果当问题规模非常大时，容易造成堆栈溢出。
	 */
	public class Program
	{
		static void Main(string[] args)
		{
			//阶乘问题
			//while (true)
			//{
			//    Console.WriteLine("\n请输入一个求阶乘的一个数：");
			//    int num = int.Parse(Console.ReadLine());
			//    Console.WriteLine("\n阶乘的结果为：" + Factorial(num));
			//}

			//进制转换问题
			Console.WriteLine("请输入一个十进制数：");
			int num = int.Parse(Console.ReadLine());
			string result = string.Empty;
			Console.WriteLine("转化的二进制为：" + ConvertToBinary(ref result, num));

			Console.ReadLine();
		}

		#region 递归的例子
		
		/*阶乘问题
		 * 相信大家在初中的时候都学过阶乘吧，比如:5!=5*4*3*2*1
			思路：根据上面的阶乘特征很容易我们就可以推导出n!=n*(n-1)*(n-2)....*2*1，
					  那么进一步其实就是: n!=n*(n-1)!，(n-1)!=(n-1)*(n-2)!。显然他是满足递归的三要素，当n的规模不大时，我们可以用递归拿下。
		 */
		static int Factorial(int n)
		{
			if (n == 1)
				return 1;
			return n * Factorial(n-1);
		}

		//进制转换问题
		/*思路：采用除2取余法，取余数为相应二进制数的最低位，然后再用商除以2得到次低位.......直到最后一次相除商为0时得到二进制的最高位，
            比如(100)10=(1100100)2，   仔细分析这个问题，会发现它是满足”递归“的三要素的，
            ① 进制转换中，数据规模会有所缩小。
            ② 当商为0时，就是我们递归的出口。
		 */
		static string ConvertToBinary(ref string str, int num)
		{
			//递的过程
			if (num == 0)
				return string.Empty;
			ConvertToBinary(ref str, num / 2);
			//归的过程
			return str += (num % 2);
		}

		#endregion
	}
}
